package com.LeeCode;

import java.util.Arrays;

/**
 * 执行操作使频率分数最大
 */

public class Code2968 {
    public static void main(String[] args) {
        int[] nums = {1, 4, 4, 2, 4};
        int k = 0;
        System.out.println(new Code2968().maxFrequencyScore(nums, k));
    }

    public int maxFrequencyScore(int[] nums, long k) {
        Arrays.sort(nums);
        int n = nums.length;

        long[] preSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        int ans = 0, left = 0;
        for (int right = 0; right < n; right++) {
            while (distanceCount(preSum, nums, left, right, (left + right) / 2) > k) {
                left++;
            }

            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    private long distanceCount(long[] sum, int[] nums, int left, int right, int index) {
        long Lnum = (long) nums[index] * (index - left) - (sum[index] - sum[left]);
        long Rnum = (sum[right + 1] - sum[index + 1]) - (long) nums[index] * (right - index);
        return Lnum + Rnum;
    }
}
